package com.leetcode;

/**
 * 219. 存在重复元素 II
 *
 * @author fy
 * @date 2022/4/8 20:39
 */
public class Solution219 {

    /**
     * 暴力法
     *
     * @param nums
     * @param k
     * @return
     */
    public boolean containsNearbyDuplicate1(int[] nums, int k) {
        if (nums == null || nums.length < 2) {
            return false;
        }
        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < Math.min(nums.length, i + k); j++) {
                if (nums[i] == nums[j]) {
                    return true;
                }
            }
        }
        return false;
    }

    public boolean containsNearbyDuplicate(int[] nums, int k) {
        if (nums == null || nums.length < 2 || k == 0) {
            return false;
        }
        int p = 0;
        int q = p + 1;
        while (p < nums.length) {
            if (p != q && q - p <= k && nums[p] == nums[q]) {
                return true;
            }
            if (q - p < k && q + 1 < nums.length) {
                q++;
            } else {
                p++;
                q = p + 1;
            }
        }
        return false;
    }

    public static void main(String[] args) {
//        int[] nums = new int[]{1, 2, 3, 1, 1, 2, 3};
//        int k = 0;

        int[] nums = new int[]{1,2,2,3};
        int k = 3;

        boolean res = new Solution219().containsNearbyDuplicate(nums, k);
        System.out.println(res);
    }

}
